We examine Lagrangian techniques for computing underapproximations offinite-time horizon, stochastic reach-avoid level-sets for discrete-time,nonlinear systems. We use the concept of reachability of a target tube in thecontrol literature to define robust reach-avoid sets which are parameterized bythe target set, safe set, and the set in which the disturbance is drawn from.We unify two existing Lagrangian approaches to compute these sets and establishthat there exists an optimal control policy of the robust reach-avoid setswhich is a Markov policy. Based on these results, we characterize the subset ofthe disturbance space whose corresponding robust reach-avoid set for the giventarget and safe set is a guaranteed underapproximation of the stochasticreach-avoid level-set of interest. The proposed approach dramatically improvesthe computational efficiency for obtaining an underapproximation of stochasticreach-avoid level-sets when compared to the traditional approaches based ongridding. Our method, while conservative, does not rely on a grid, implyingscalability as permitted by the known computational geometry constraints. Wedemonstrate the method on two examples: a simple two-dimensional integrator,and a space vehicle rendezvous-docking problem.
展开▼
